{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def moveZeroes(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: None Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        l = len(nums)\n",
    "        non_zero_pair = []\n",
    "        left = 0\n",
    "        right = 0\n",
    "        while right < l:\n",
    "            while left < l and nums[left] == 0:\n",
    "                left = left + 1            \n",
    "            # The last block are zeros\n",
    "            if left == l:\n",
    "                break\n",
    "            right = left\n",
    "            while right < l and nums[right] != 0:\n",
    "                right = right + 1\n",
    "            \n",
    "            non_zero_pair.append((left, right))\n",
    "            # Scan the next block\n",
    "            left = right\n",
    "\n",
    "        cur = 0\n",
    "        for left, right in non_zero_pair:\n",
    "            nums[cur:cur+(right-left)] = nums[left:right]\n",
    "            cur = cur + right - left\n",
    "        nums[cur:] = [0]*(l-cur)\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [],
   "source": [
    "s = Solution()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[-1278640323,\n",
       " 349172856,\n",
       " 1873509219,\n",
       " 2086212774,\n",
       " -1001344505,\n",
       " -61069976,\n",
       " 746705870,\n",
       " -173131555,\n",
       " -1898820175,\n",
       " 802998965,\n",
       " -916055673,\n",
       " 344084770,\n",
       " -1664334387,\n",
       " -1886907515,\n",
       " 171107295,\n",
       " -2065649057,\n",
       " -1628881728,\n",
       " -1900147601,\n",
       " -342880452,\n",
       " -2037018488,\n",
       " -104769833,\n",
       " 374941067,\n",
       " 536619007,\n",
       " -298730590,\n",
       " -1594869648,\n",
       " 1855390876,\n",
       " 904830187,\n",
       " -809158725,\n",
       " -1923547142,\n",
       " 1340100626,\n",
       " 953054962,\n",
       " 1195315949,\n",
       " 1281604841,\n",
       " 58893147,\n",
       " 2109018765,\n",
       " -928102085,\n",
       " -348541385,\n",
       " 1222161829,\n",
       " -319162010,\n",
       " -1229679355,\n",
       " 635148638,\n",
       " 1343064576,\n",
       " 1235762604,\n",
       " 808863719,\n",
       " -1399893584,\n",
       " 262412042,\n",
       " 852755753,\n",
       " 2122991509,\n",
       " -439470997,\n",
       " 1284528791,\n",
       " -1255542315,\n",
       " 1381099667,\n",
       " -612012457,\n",
       " 1158700697,\n",
       " -1931432559,\n",
       " -382355048,\n",
       " 386876825,\n",
       " -410932959,\n",
       " -881191573,\n",
       " 2108126972,\n",
       " 66895034,\n",
       " 571651517,\n",
       " -807893976,\n",
       " 1722089493,\n",
       " -686780868,\n",
       " 1749687634,\n",
       " -578975209,\n",
       " 789489601,\n",
       " -910418255,\n",
       " -1284665174,\n",
       " -95463312,\n",
       " 1575944713,\n",
       " -2147416931,\n",
       " -1895923493,\n",
       " -1305298050,\n",
       " 536339908,\n",
       " 1613600218,\n",
       " 1380993216,\n",
       " -1389605087,\n",
       " -1561287616,\n",
       " 586284425,\n",
       " 1988071814,\n",
       " -411494200,\n",
       " -1468158575,\n",
       " -117756488,\n",
       " -2078953097,\n",
       " 2112227122,\n",
       " -1554628163,\n",
       " 1073601549,\n",
       " -19456,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0]"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s.moveZeroes([-1278640323,349172856,1873509219,2086212774,0,-1001344505,-61069976,746705870,-173131555,-1898820175,802998965,-916055673,344084770,-1664334387,-1886907515,171107295,-2065649057,-1628881728,-1900147601,-342880452,-2037018488,-104769833,0,0,374941067,536619007,-298730590,-1594869648,1855390876,904830187,-809158725,-1923547142,1340100626,953054962,1195315949,0,1281604841,58893147,2109018765,-928102085,-348541385,1222161829,-319162010,-1229679355,635148638,1343064576,1235762604,808863719,-1399893584,262412042,852755753,2122991509,-439470997,1284528791,0,-1255542315,1381099667,-612012457,1158700697,-1931432559,-382355048,386876825,-410932959,-881191573,2108126972,66895034,571651517,-807893976,1722089493,0,-686780868,1749687634,-578975209,789489601,-910418255,-1284665174,-95463312,1575944713,-2147416931,-1895923493,-1305298050,536339908,1613600218,1380993216,-1389605087,-1561287616,586284425,1988071814,-411494200,-1468158575,-117756488,-2078953097,2112227122,-1554628163,1073601549,0,-19456])"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
